package 剑指Offer1;

import java.util.LinkedList;
import java.util.List;

public class _34二叉树中和为某一值的路径 {
    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
    }

    private List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
         if(root == null) return res;
         preOrder(root,target,new LinkedList<>());
         return res;
    }

    private void preOrder(TreeNode root,int target,LinkedList<Integer> path){
        if(root == null) return;
        int result = target - root.val;

        if(root.left == null && root.right == null){ //必须是叶子节点才行
           if(result == 0){
              path.addLast(root.val);
              res.add(new LinkedList<>(path));
              path.removeLast();
           }
           return; //在叶子节点这里返回
        }

        path.addLast(root.val);
        preOrder(root.left,result,path);
        path.removeLast();

        path.addLast(root.val);
        preOrder(root.right,result,path);
        path.removeLast();

    }
}
